package com.sheng.leetcode.year2022.swordfingeroffer.day20;

import org.junit.Test;

/**
 * @author liusheng
 * @date 2022/09/19
 *<p>
 * 剑指 Offer 16. 数值的整数次方<p>
 *<p>
 * 实现pow(x,n)，即计算 x 的 n 次幂函数（即，x^n）。不得使用库函数，同时不需要考虑大数问题。<p>
 *<p>
 * 示例 1：<p>
 * 输入：x = 2.00000, n = 10<p>
 * 输出：1024.00000<p>
 *<p>
 * 示例 2：<p>
 * 输入：x = 2.10000, n = 3<p>
 * 输出：9.26100<p>
 *<p>
 * 示例 3：<p>
 * 输入：x = 2.00000, n = -2<p>
 * 输出：0.25000<p>
 * 解释：2^-2 = 1/2^2 = 1/4 = 0.25<p>
 *<p>
 * 提示：<p>
 *<p>
 * -100.0 <x< 100.0<p>
 * -2^31<= n <=2^31-1<p>
 * -10^4<= x^n<= 10^4<p>
 *<p>
 * 注意：本题与主站 50 题相同：<a href="https://leetcode-cn.com/problems/powx-n/">...</a><p>
 *<p>
 * 来源：力扣（LeetCode）<p>
 * 链接：<a href="https://leetcode.cn/problems/shu-zhi-de-zheng-shu-ci-fang-lcof">...</a><p>
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。<p>
 */
public class Sword0016 {

    @Test
    public void test01() {
//        double x = 2.0d;
//        int n = 10;
//        double x = 2.1d;
//        int n = 3;
        double x = 2.0d;
        int n = -2;
        System.out.println(new Solution16().myPow(x, n));
    }
}
class Solution16 {

    public double myPow(double x, int n) {
        long N = n;
        return N >= 0 ? quickMul(x, N) : 1.0 / quickMul(x, -N);
    }
    public double quickMul(double x, long N) {
        if (N == 0) {
            return 1.0;
        }
        // 递归
        double y = quickMul(x, N / 2);
        return N % 2 == 0 ? y * y : y * y * x;
    }
    // 超时
//    public double myPow(double x, int n) {
//        // 首先判断 n 是正数还是负数
//        double ans = 1.0d;
//        boolean flag = false;
//        if (n == 0) {
//            return 1;
//        } else if (n < 0) {
//            flag = true;
//            n = -n;
//        }
//        while (n > 0) {
//            ans *= x;
//            n--;
//        }
//        if (flag) {
//            ans = 1 / ans;
//        }
//        return ans;
//    }
}

//class Solution {
//    public double myPow(double x, int n) {
//        long N = n;
//        return N >= 0 ? quickMul(x, N) : 1.0 / quickMul(x, -N);
//    }
//
//    public double quickMul(double x, long N) {
//        if (N == 0) {
//            return 1.0;
//        }
//        double y = quickMul(x, N / 2);
//        return N % 2 == 0 ? y * y : y * y * x;
//    }
//}
//
//作者：LeetCode-Solution
//链接：https://leetcode.cn/problems/shu-zhi-de-zheng-shu-ci-fang-lcof/solution/shu-zhi-de-zheng-shu-ci-fang-by-leetcode-yoqr/
//来源：力扣（LeetCode）
//著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
